package 链表系列;

public class GetIntersectionNode {

    //暴力双循环
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        ListNode dummyHeadA = new ListNode(-1,headA);
//        ListNode dummyHeadB = new ListNode(-2,headB);
//
//        for(ListNode curA = dummyHeadA; curA != null; curA = curA.next){
//            for(ListNode curB = dummyHeadB; curB != null; curB = curB.next){
//                if(curA.next == curB.next && curB.next!=null && curA.next!=null){
//                    return curA.next;
//                }
//                // System.out.println("curA的值为："+curA.val+",curA的next为:"+curA.next);
//                // System.out.println("curB的值为："+curB.val+",curB的next为:"+curB.next);
//            }
//        }
//        return null;
//    }

    //- 时间复杂度：$O(n + m)$
    //- 空间复杂度：$O(1)$
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        int lenA = 0, lenB = 0;
        while (curA != null){   //求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null){   //求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        //让curA为最长链表的头，lenA为长度
        if (lenB > lenA){
            //1. swap(lenA,lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap(curA,curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        //求长度差
        int gap = lenA - lenB;
        //让curA和curB在同一起点上（末尾位置对齐）
        while(gap-- > 0){
            curA = curA.next;
        }
        //遍历curA 和 curB，遇到相同则直接返回
        while (curA != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
